package com.ctl.algorithm;

import java.util.*;

/**
 * <p>Title: Test</p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2019</p>
 * <p>Company: www.ctl.com</p>
 * https://mp.weixin.qq.com/s/wraIMEVGz4GcNxe5WtxPRQ
 * 解数独-回溯算法解决
 * 编写一个程序，通过填充空格来解决数独问题。
 * 数独的解法需 遵循如下规则：
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 9个 3x3 宫内只能出现一次。
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * 输入：board = [
 * ["5","3",".",".","7",".",".",".","."],
 * ["6",".",".","1","9","5",".",".","."],
 * [".","9","8",".",".",".",".","6","."],
 * ["8",".",".",".","6",".",".",".","3"],
 * ["4",".",".","8",".","3",".",".","1"],
 * ["7",".",".",".","2",".",".",".","6"],
 * [".","6",".",".",".",".","2","8","."],
 * [".",".",".","4","1","9",".",".","5"],
 * [".",".",".",".","8",".",".","7","9"]]
 * 输出：[
 * ["5","3","4","6","7","8","9","1","2"],
 * ["6","7","2","1","9","5","3","4","8"],
 * ["1","9","8","3","4","2","5","6","7"],
 * ["8","5","9","7","6","1","4","2","3"],
 * ["4","2","6","8","5","3","7","9","1"],
 * ["7","1","3","9","2","4","8","5","6"],
 * ["9","6","1","5","3","7","2","8","4"],
 * ["2","8","7","4","1","9","6","3","5"],
 * ["3","4","5","2","8","6","1","7","9"]]
 *
 * @author ctl
 * @version 1.1
 * @date 2023-02-07 17:28
 */


public class Sudoku9_9 {
    /**
     * 二维数组x轴是否可用
     *
     * @param array9_9
     * @param str
     * @return
     */
    public static boolean rowCanUse(String[][] array9_9, String str, int row, int col) {
        for (int i = 0; i < array9_9[row].length; i++) {
            if (array9_9[row][i].equals(str)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 二维数组y轴是否可用
     *
     * @param array9_9
     * @param str
     * @return
     */
    public static boolean colCanUse(String[][] array9_9, String str, int row, int col) {
        for (int i = 0; i < array9_9[col].length; i++) {
            if (array9_9[i][col].equals(str)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 9个小二维数组中自己所在的小数组是否可用
     *
     * @param array9_9
     * @param str
     * @return
     */
    public static boolean small9CanUse(String[][] array9_9, String str, int row, int col) {
        //9*9中的9个3*3的范围
        int startRow = (row / 3) * 3;
        int endRow = (row / 3) * 3 + 2;
        int startCol = (col / 3) * 3;
        int endCol = (col / 3) * 3 + 2;
        for (int i = startRow; i <= endRow; i++) {
            for (int j = startCol; j <= endCol; j++) {
                if (array9_9[i][j].equals(str)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * x,y,small9都可以用
     *
     * @param array9_9
     * @param str
     * @param row
     * @param col
     * @return
     */
    public static boolean canUseAll(String[][] array9_9, String str, int row, int col) {
        if (rowCanUse(array9_9, str, row, col) && colCanUse(array9_9, str, row, col) && small9CanUse(array9_9, str, row, col)) {
            return true;
        }
        return false;
    }

    /**
     * x,y,small9都可以用
     *
     * @param array9_9
     * @param point
     * @return
     */
    public static boolean canUseAll(String[][] array9_9, Point point) {
        String str = point.getArray().get(point.getCurrentIndex());
        int row = point.x;
        int col = point.y;
        if (rowCanUse(array9_9, str, row, col) && colCanUse(array9_9, str, row, col) && small9CanUse(array9_9, str, row, col)) {
            return true;
        }
        return false;
    }

    static String[] array9 = new String[]{"1", "2", "3", "4", "5", "6", "7", "8", "9"};

    /**
     * 输出二维数组
     *
     * @param array9_9_back
     */
    private static void print9_9_array(String[][] array9_9_back) {
        System.out.println();
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.deepToString(array9_9_back[i]));
        }
    }

    public static void main(String[] args) {
        String blank = ".";
        List<Point> pointList = new ArrayList<>();
        String[][] array9_9 = new String[][]{{"5", "3", ".", ".", "7", ".", ".", ".", "."}, {"6", ".", ".", "1", "9", "5", ".", ".", "."}, {".", "9", "8", ".", ".", ".", ".", "6", "."}, {"8", ".", ".", ".", "6", ".", ".", ".", "3"}, {"4", ".", ".", "8", ".", "3", ".", ".", "1"}, {"7", ".", ".", ".", "2", ".", ".", ".", "6"}, {".", "6", ".", ".", ".", ".", "2", "8", "."}, {".", ".", ".", "4", "1", "9", ".", ".", "5"}, {".", ".", ".", ".", "8", ".", ".", "7", "9"}};
        String[][] array9_9_back = new String[][]{{"5", "3", ".", ".", "7", ".", ".", ".", "."}, {"6", ".", ".", "1", "9", "5", ".", ".", "."}, {".", "9", "8", ".", ".", ".", ".", "6", "."}, {"8", ".", ".", ".", "6", ".", ".", ".", "3"}, {"4", ".", ".", "8", ".", "3", ".", ".", "1"}, {"7", ".", ".", ".", "2", ".", ".", ".", "6"}, {".", "6", ".", ".", ".", ".", "2", "8", "."}, {".", ".", ".", "4", "1", "9", ".", ".", "5"}, {".", ".", ".", ".", "8", ".", ".", "7", "9"}};
        extracted(blank, pointList, array9_9);
        print9_9_array(array9_9);
        print9_9_array(array9_9_back);
        System.out.println(pointList);

        array9_9 = new String[][]{{"5", "1", ".", ".", "7", ".", ".", ".", "."}, {"6", "2", ".", "1", "9", "5", ".", ".", "."}, {".", "9", "8", ".", ".", ".", ".", "6", "."}, {"8", ".", ".", ".", "6", ".", ".", ".", "3"}, {"4", ".", ".", "8", ".", "3", ".", ".", "1"}, {"7", ".", ".", ".", "2", ".", ".", ".", "6"}, {".", "6", ".", ".", ".", ".", "2", "8", "."}, {".", ".", ".", "4", "1", "9", ".", ".", "5"}, {".", ".", ".", ".", "8", ".", ".", "7", "9"}};
        array9_9_back = new String[][]{{"5", "1", ".", ".", "7", ".", ".", ".", "."}, {"6", "2", ".", "1", "9", "5", ".", ".", "."}, {".", "9", "8", ".", ".", ".", ".", "6", "."}, {"8", ".", ".", ".", "6", ".", ".", ".", "3"}, {"4", ".", ".", "8", ".", "3", ".", ".", "1"}, {"7", ".", ".", ".", "2", ".", ".", ".", "6"}, {".", "6", ".", ".", ".", ".", "2", "8", "."}, {".", ".", ".", "4", "1", "9", ".", ".", "5"}, {".", ".", ".", ".", "8", ".", ".", "7", "9"}};
        extracted(blank, pointList, array9_9);
        print9_9_array(array9_9);
        print9_9_array(array9_9_back);
        System.out.println(pointList);
    }

    private static void extracted(String blank, List<Point> pointList, String[][] array9_9) {
        pointList.clear();
        //print9_9_array(array9_9);
        getPointArray(blank, pointList, array9_9);
        pointOneFill(pointList, array9_9);
        //print9_9_array(array9_9);
        //双向队列
        ListIterator<Point> pointListIterator = pointList.listIterator();
        int times = 0;
        boolean errorInput = false;
        forlabel1:
        while (pointListIterator.hasNext()) {
            //System.out.println("times:" + (++times));
            Point cur = pointListIterator.next();
            if (canUseAll(array9_9, cur)) {
                //满足尝试下一个元素
                array9_9[cur.getX()][cur.getY()] = cur.getArray().get(cur.getCurrentIndex());
                //print9_9_array(array9_9);
                continue;
            } else {
                //不满足从该点位可选列表中选取其他尝试
                boolean goToNext = false;
                int incrementAndGet = cur.incrementAndGet();
                forlabel2:
                for (int i = incrementAndGet; i < cur.getArray().size(); i++) {
                    if (canUseAll(array9_9, cur)) {
                        goToNext = true;
                        break forlabel2;
                    } else {
                        cur.incrementAndGet();
                    }
                }
                if (goToNext) {
                    //后面的备选成功
                    array9_9[cur.getX()][cur.getY()] = cur.getArray().get(cur.getCurrentIndex());
                    //print9_9_array(array9_9);
                    continue forlabel1;
                } else {
                    //所有元素都不可行回溯上个
                    pointListIterator.previous();
                    cur.setCurrentIndex(0);
                    array9_9[cur.getX()][cur.getY()] = ".";
                    while (pointListIterator.hasPrevious()) {
                        Point parent = pointListIterator.previous();
                        if (parent.getCurrentIndex() < parent.getArray().size() - 1) {
                            //如果回溯到上一个元素且上一个元素还有备选则跳出while使用该备选去回溯
                            parent.incrementAndGet();
                            array9_9[parent.getX()][parent.getY()] = ".";
                            //print9_9_array(array9_9);
                            break;
                        } else {
                            //如果没有备选继续回溯到上上一个如果回溯到第一个待选且没有可供使用的则退出(一但break说明算法有误或者初始数据有误)
                            if (pointListIterator.hasPrevious()) {
                                parent.setCurrentIndex(0);
                                array9_9[parent.getX()][parent.getY()] = ".";
                                //print9_9_array(array9_9);
                            } else {
                                //正常永远不会走到该break
                                System.err.println("输入数组不对" + parent);
                                errorInput = true;
                                break forlabel1;
                            }
                        }
                    }
                }
            }
        }
        if (!errorInput) {
            for (int i = 0; i < pointList.size(); i++) {
                Point point = pointList.get(i);
                array9_9[point.getX()][point.getY()] = point.getArray().get(point.getCurrentIndex());
            }
        }
    }

    /**
     * 点位只有一个被选那么先直接填充然后从待填充列表删除
     *
     * @param pointList
     * @param array9_9
     */
    private static void pointOneFill(List<Point> pointList, String[][] array9_9) {
        Iterator<Point> iterator = pointList.iterator();
        while (iterator.hasNext()) {
            Point next = iterator.next();
            if (next.getArray().size() == 1) {
                array9_9[next.getX()][next.getY()] = next.getArray().get(0);
                iterator.remove();
            }
        }
    }

    /**
     * 获取每个代填位置可以填充的数字列表(供回溯使用)
     *
     * @param blank
     * @param pointList
     * @param array9_9
     */
    private static void getPointArray(String blank, List<Point> pointList, String[][] array9_9) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (array9_9[i][j].equals(blank)) {
                    Point point = new Point().withX(i).withY(j);
                    pointList.add(point);
                    for (int k = 0; k < array9.length; k++) {
                        String canUse = array9[k];
                        if (canUseAll(array9_9, canUse, i, j)) {
                            point.getArray().add(canUse);
                        }
                    }
                }
            }
        }
    }


}

class Point {
    int x;
    int y;
    int currentIndex = 0;

    public int incrementAndGet() {
        return ++currentIndex;
    }

    List<String> array = new ArrayList<>();

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    public Point withX(int x) {
        this.x = x;
        return this;
    }

    public Point withY(int y) {
        this.y = y;
        return this;
    }

    public int getCurrentIndex() {
        return currentIndex;
    }

    public void setCurrentIndex(int currentIndex) {
        this.currentIndex = currentIndex;
    }

    public List<String> getArray() {
        return array;
    }

    public void setArray(List<String> array) {
        this.array = array;
    }

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                ", currentIndex=" + currentIndex +
                ", array=" + array +
                '}';
    }
}